1. Field of the Invention
This invention pertains generally to video decoding, and more particularly to a method of performing decoding operations that are particularly well-suited for use in multiprocessor environments.
2. Description of the Background Art
A number of formats are currently available within which video may be encoded. One such format is the MPEG-4 video coding standard which has been established to support object-oriented coding mechanisms. MPEG-4 is generally considered a highly promising video coding standard for a number of video applications. The promise of MPEG-4 is at least partially the result of the numerous tools which are currently being made available for MPEG-4 coding. In addition to providing an object-oriented coding scheme, a high coding efficiency can be achieved utilizing MPEG-4 with respect to encoded bit-rate and video quality. The efficiency of MPEG-4 is primarily the result of incorporating advanced coding schemes which have been lacking within other video coding standards, such as MPEG-1 and MPEG-2. It should, however, be recognized that the use of these advanced encoding techniques complicates the decoding process within MPEG-4, and formats of a similar architecture, thereby complicating the implementation of decoders which operate on these video bit-streams in real time.
Recently, industry resources have been increasingly directed at designing fast decoders, such as for MPEG-4, which may be utilized to provide real-time decoding within a number of applications. These efforts, however, have been largely directed at decoders which integrate a single fast processing element, or a pair of fast processing elements, and have not addressed solving the problem in response to the use of decoders which integrate an arbitrary number of lower cost processors.
Coefficients utilized within the MPEG4 format are encoded utilizing DC and AC predictions which often reference information from previously encoded macroblocks. It will be appreciated therefore that decoding of these macroblocks requires accessing information about other, temporally displaced, macroblocks. Motion vectors are also predicted from the motion vectors of adjacent macroblocks in similar ways. Due to such predictions, the decoding of a macroblock requires access to the information from previously decoded macroblocks. This requirement implies that the decoding of macroblocks within the incoming bit-stream must be performed sequentially from the first macroblock to the last macroblock which is directed at the video object plane (VOP). Conventional decoders are generally constrained to this sequential macroblock processing paradigm.
FIG. 1 illustrates an example of a decoder implemented for an MPEG-4 bit-stream in which decoding operations are performed on a block-by-block basis. Header and data information is first decoded through variable length decoding (VLD) from within the encoded MPEG-4 bit-stream, and then a prediction direction is determined (PDD) for use by subsequent operations. The data is then typically subject to inverse scanning (IS), inverse DC prediction (IDCP), inverse AC prediction (IACP), inverse quantization (IQ), inverse discrete-transform (IDCT), and finally, motion compensation in association with the video object plane (VOP). As a result of the dependence on prediction direction, it would be difficult to separate the decoding operations for execution on multiple processors to expedite the decoding process.
It will be appreciated that during decoding, the inverse-scanning (IS) process converts the decoded one-dimensional array into a two-dimensional array for further processing. The syntax of the MPEG-4 bit-stream provides at least three different inverse-scanning methods, specifically: zigzag_scan, alternate_horizontal_scan, and alternate_vertical_scan. The bit-stream itself does not include information as to which inverse-scanning method should be chosen. The selection of a proper scanning method should, however, be based on the value of the decoded DC coefficients of the current and neighboring blocks within the decoder. It should also be noted that the prediction direction decision (PDD) must acquire the DC value from previously decoded blocks F[n]. The prediction direction determined by executing PDD is utilized within the inverse DC prediction (IDCP) operation and the inverse AC prediction (IACP) operation. In these two procedures, the previously decoded data, F[n−1] is required in addition to QFA[n−1] which is also utilized.
The design of conventional decoders is constrained by the high-level of data dependency within the encoded bit-stream, which has resulted in the general adoption of a sequential decoding paradigm. This conventional sequential-decoding paradigm, however, is not readily extendable to multiprocessing decoder designs, in particular those which incorporate an arbitrary number of processing elements, such as three or more processors. Decoders have been previously considered which retain this sequential paradigm while employing a pair of processors according to a conventional operation slicing methodology. These slicing methods significantly hinder realizable performance gains, because of the high execution overheads involved in slicing a substantially sequential operation. In attempting to move beyond two processors, the execution overhead increases drastically which substantially limits the effective gains.
The current decoding methods which include prediction direction determination prior to the AC predictions also impact decoding performance, in particular the speed with which inverse AC predictions may be executed. Video bit-streams are often encoded with DC and AC coefficients which are determined in response to DC and AC predictions to provide a high efficiency encoding method. For example, DC and AC coefficients are utilized within INTRA macroblocks within an MPEG4 video bit-stream. On the decoder side, however, the prediction direction must be determined prior to utilizing these DC and AC coefficients within an inverse prediction operation, as is shown in FIG. 1.
A prediction direction, for either DC or AC, is obtained based on a comparison of the horizontal and vertical DC gradients surrounding the block to be decoded. FIG. 2 illustrates a current block X surrounded to the left by a block A, above-left by block B, and above by block C. The inverse-quantized DC values of the previously decoded blocks, represented by F[0][0], are utilized to ascertain the direction of DC and AC prediction as follows:
if (|FA[0][0]−FB[0][0]|<|FB[0][0]−FC[0][0]|)                predict from block C        
else                predict from block A        
The adaptive DC prediction method involves selection of either the F[0][0] value of the immediately prior block or that of the block immediately above from within the previous row of blocks, in response to the direction as determined above.
if (prediction is from block C)                QFX[0][0]=PQFX[0][0]+FC[0][0]//dc_scalar        
else                QFX[0][0]=PQFX[0][0]+FA[0][0]//dc_scalar        
In the above relation, the value dc_scalar is obtained by quantization of the step-size, which is independently repeated for every block within the macroblock using the appropriate horizontally proximal block A and vertically proximal block C.
To predict the co-sited AC coefficient of the current block, shown by X, coefficients are utilized from either the first row, or the first column, from a previously coded block. When analyzed on a block basis, the optimum vertical or horizontal direction for DC coefficient prediction is also utilized to select the direction for AC coefficient prediction. It will be appreciated, for instance, that it becomes possible to predict each block independently of previous adjacent vertical and horizontal blocks within the given macroblock. FIG. 3 depicts neighboring blocks and coefficients utilized within an AC prediction.
Therefore, a need exists for a texture decoding method and AC prediction method that may be efficiently applied to multiprocessing decoder system environments. The present invention satisfies that needs, as well as others, and overcomes the deficiencies of previously developed texture decoding methods.